#include "../chtree1.h"
#include <stdio.h>

/**
 * 实现树的前序遍历
 * @param p    指向树根结点的指针变量
 * @return void
 */
void preorder(tree p)
{
    int i;
    if (p)
    {
        printf("%c", p->data); // 访问根节点
        for (i = 0; i < m; i++)
        {
            preorder(p->child[i]); // 递归遍历子树
        }
    }
}

/**
 * 实现树的后序遍历
 * @param p    指向树根结点的指针变量
 * @return void
 */
void postorder(tree p)
{
    int i;
    if (p)
    {
        for (i = 0; i < m; i++)
        {
            postorder(p->child[i]); // 递归遍历子树
        }
        printf("%c", p->data); // 访问根节点
    }
}

/**
 * 根据树的前序遍历结果建立一颗 3 度树
 * @return 树的根结点指针
 */
tree createtree()
{
    int i = 0;
    char ch;
    tree t;

    if ((ch = getchar()) == '#')
    {
        t = NULL;
    }
    else
    {
        t = (tree)malloc(sizeof(tree));
        t->data = ch;
        for (i = 0; i < m; i++)
        {
            t->child[i] = createtree();
        }
    }
    return t;
}

/**
 * 实现树的层次遍历t
 * @param t    指向树根结点的指针变量
 * @return void
 */
void levelorder(tree t)
{
    // 存放等待访问的结点的队列
    tree queue[100];
    // f、r 分别为对头和队尾指针
    int f, r, i;
    tree p;
    f = r = 0;
    queue[0] = t;

    while (f < r)
    {
        p = queue[f++];
        // 访问结点
        printf("%c", p->data);
        // 将刚被访问的结点的所有孩子结点入队
        for (i = 0; i < m; i++)
        {
            if (p->child[i])
            {
                queue[r] = p->child[i];
                ++r;
            }
        }
    }
}